package 代码随想录_动态规划.完全背包;

/**
 * @author zx
 * @create 2022-05-31 16:11
 * 题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。
 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
 * 2.确定递推公式
 *  递推公式：dp[j] =  min(dp[j - coins[i]] + 1, dp[j]);
 * 3.dp数组如何初始化
 *  凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
 *  考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
 *  所以下标非0的元素都是应该是最大值。
 * 4.确定遍历顺序
 *  本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。。
 *  所以本题并不强调集合是组合还是排列。
 *  如果求组合数就是外层for循环遍历物品，内层for遍历背包。
 *  如果求排列数就是外层for遍历背包，内层for循环遍历物品。
 *  所以采用本人(zx)喜欢的方式：coins(物品)放在外循环,target(背包)在内循环.且内循环正序.
 * 5.举例推导dp数组
 *
 */
public class 零钱兑换_322 {
    /**
     * @return 背
     */
    public int coinChange(int[] coins, int amount) {
        //dp[j]：凑成amount需要的最少硬币个数
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for(int i = 1;i < dp.length;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i = 0;i < coins.length;i++){
            for(int j = coins[i];j <= amount;j++){
                //dp[j - coins[i]] != Integer.MAX_VALUE:可能会无解
                if(dp[j - coins[i]] != Integer.MAX_VALUE){//dp[j - coins[i]]是初始值则直接跳过
                    dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);
                }
            }
        }
        if(dp[amount] == Integer.MAX_VALUE){
            return -1;
        }
        return dp[amount];
    }
}
